package top.whk0710.swordoffer._19PrintMatrix;

import java.util.*;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.Executors;

/**
 * 牛客网剑指offer第19题
 * 输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，
 * 例如，如果输入如下4 X 4矩阵： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 
 * 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.
 * */
public class Solution {

    public static void main(String[] args){
    	int [][] matrix = {
    			{1},
    			{2},
    			{3},
    			{4},
    			{5}
    	};
        printMatrix(matrix);
    }

    /**
     * 一圈一圈的打印，一开始没想出来，过了一天
     * 然后突然想出来怎么做了，哈哈
     * 就是不知道怎么判断走几圈，看了牛客网分析知道了。
     * O(MN)
     * */
    public static ArrayList<Integer> printMatrix(int [][] matrix) {
        if (matrix == null) return null;
        ArrayList<Integer> list = new ArrayList<>();
        //考虑m*n矩阵要打印几次？取短的一边+1除以2
        int circle = ((matrix.length > matrix[0].length ? matrix[0].length : matrix.length) + 1)/2;
        for(int start=0;start<circle;start++){
        	//打印第一行
            for(int i=start;i<matrix[0].length - start;i++){
            	//System.out.println(matrix[start][i]);
            	list.add(matrix[start][i]);
            }
            //打印col_length-1列除了[start][col_length-1-start]元素
            for(int i=start + 1;i<matrix.length-start;i++){
            	//System.out.println(matrix[i][matrix[0].length-1-start]);
            	list.add(matrix[i][matrix[0].length-1-start]);
            }
            //要否定matrix.length-1-start = start的情况,否则会重复打印
            //倒序打印最后一行除了[row_length-1][col_length-1]的元素
            for(int i=matrix[0].length-2-start;i>=start && matrix.length-1-start != start;i--){
            	//System.out.println(matrix[matrix.length-1-start][i]);
            	list.add(matrix[matrix.length-1-start][i]);
            }
            //要否定matrix[0].length-1-start = start的情况,否则会重复打印
            //打印第start列除了[row_length-1-start][start]和[start][start]的元素
            for(int i=matrix.length-2-start;i>start && matrix[0].length-1-start != start;i--){
            	//System.out.println(matrix[i][start]);
            	list.add(matrix[i][start]);
            }
        }
        return list;
    }
}
